package cn.jdemo.algorithm.dynamicProgramming;

/**
 * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *
 * --- 可买卖2次
 *
 * 动态规划
 * 1.定义
 *  dp[i][0],不定义
 *  dp[i][1],第1次持有
 *  dp[i][2],第1次不持有
 *  dp[i][3],第2次持有
 *  dp[i][4],第2次不持有
 * 2.推导公式
 *  dp[i][1],第1次,第i天持有最大利润
 *      第i天不持有股票，则买入 - price[i]
 *      第i天持有股票，则不可以买入,dp[i-1][1]
 *  --- dp[i][1] = max(dp[i-1][1],-price[i])
 *  dp[i][2],第1次,第i天不持有最大利润
 *      第i天不持有股票，则不可卖出，那么当天利润是 dp[i-1][2]
 *      第i天持有股票，则卖出 dp[i-1][1] + price[i]
 *  --- dp[i][2] = Max(dp[i-1][2],dp[i-1][1] + price[i])
 *  dp[i][3],第2次,第i天持有最大利润
 *      第i天不持有股票，则买入 dp[i-1][2] - price[i]
 *      第i天持有股票，则不可以买入,dp[i-1][3]
 *  --- dp[i][3] = Max(dp[i-1][2] - price[i],dp[i-1][3])
 *  dp[i][4],第2次,第i天不持有最大利润
 *      第i天不持有股票，则不可卖出，那么当天利润是 dp[i-1][4]
 *      i天持有股票，则卖出 dp[i-1][3] + price[i]
 *  --- dp[i][4] = Max(dp[i-1][3] + price[i],dp[i-1][4])
 * 3.初始化
 *      dp[0][1] = -prices[0];
 *      dp[0][2] = 0;
 *      dp[0][3] = -prices[0];// 不用管第几次，现在手头上没有现金，只要买入，现金就做相应的减少?
 *      dp[0][4] = 0;
 * 4.遍历顺序
 *  从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。
 * 5.样例：[3,3,5,0,0,3,1,4]
 *      dp[i][0]  dp[i][1]  dp[i][2]  dp[i][3]  dp[i][4]
 *    0     0        -3         0         0         0
 *    1     0        -3         0         -3        0
 *    2     0        -3         2         -3        2
 *    3     0         0         2         2         2
 *    4     0         0         2         2         2
 *    5     0         0         3         2         5
 *    6     0         0         3         2         5
 *    7     0         0         4         2         6
 *
 */
public class Stock3 {
    public static void main(String[] args) {
        int[] prices = {3,3,5,0,0,3,1,4};
        int res = new Stock3().maxProfit(prices);
        System.out.println(res);
    }

    public int maxProfit(int[] prices) {
        int length = prices.length;
        int[][] dp1 = new int[length][5];
        int[][] dp2 = new int[length][5];
        int[][] dp3 = new int[length][5];
        int[][] dp4 = new int[length][5];
        dp1[0][1] = -prices[0];
        dp3[0][3] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp1[i][1] = Math.max(dp1[i - 1][1], -prices[i]);
            dp2[i][2] = Math.max(dp2[i-1][2], dp1[i-1][1]+prices[i]);
            dp3[i][3] = Math.max(dp3[i-1][3], dp2[i-1][2]-prices[i]);
            dp4[i][4] = Math.max(dp4[i-1][4], dp3[i-1][3]+prices[i]);
        }
        return dp4[length-1][4];
    }

}
